{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #UTF-8 Validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validUtf8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #UTF-8 编码验证"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示数据的整数数组&nbsp;<code>data</code>&nbsp;，返回它是否为有效的 <strong>UTF-8</strong> 编码。</p>\n",
    "\n",
    "<p><strong>UTF-8</strong> 中的一个字符可能的长度为 <strong>1 到 4 字节</strong>，遵循以下的规则：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>对于 <strong>1 字节</strong>&nbsp;的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。</li>\n",
    "\t<li>对于 <strong>n 字节</strong>&nbsp;的字符 (n &gt; 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。</li>\n",
    "</ol>\n",
    "\n",
    "<p>这是 UTF-8 编码的工作方式：</p>\n",
    "\n",
    "<pre>\n",
    "<code>      </code>Number of Bytes<code>  |        UTF-8 octet sequence\n",
    "                       |              (binary)\n",
    "   --------------------+---------------------------------------------\n",
    "            1          | 0xxxxxxx\n",
    "            2          | 110xxxxx 10xxxxxx\n",
    "            3          | 1110xxxx 10xxxxxx 10xxxxxx\n",
    "            4          | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx\n",
    "</code></pre>\n",
    "\n",
    "<p><code>x</code>&nbsp;表示二进制形式的一位，可以是 <code>0</code>&nbsp;或 <code>1</code>。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输入是整数数组。只有每个整数的 <strong>最低 8 个有效位</strong> 用来存储数据。这意味着每个整数只表示 1 字节的数据。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>data = [197,130,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>数据表示字节序列:<strong>11000101 10000010 00000001</strong>。\n",
    "这是有效的 utf-8 编码，为一个 2 字节字符，跟着一个 1 字节字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>data = [235,140,4]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>数据表示 8 位的序列: <strong>11101011 10001100 00000100</strong>.\n",
    "前 3 位都是 1 ，第 4 位为 0 表示它是一个 3 字节字符。\n",
    "下一个字节是开头为 10 的延续字节，这是正确的。\n",
    "但第二个延续字节不以 10 开头，所以是不符合规则的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= data.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= data[i] &lt;= 255</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [utf-8-validation](https://leetcode.cn/problems/utf-8-validation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [utf-8-validation](https://leetcode.cn/problems/utf-8-validation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[197,130,1]', '[235,140,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validUtf8(self, data: List[int]) -> bool:\r\n",
    "        flag = True\r\n",
    "        n = len(data)\r\n",
    "        i = 0\r\n",
    "        while True:\r\n",
    "            if i >= n:\r\n",
    "                break\r\n",
    "            if data[i] <= 128:\r\n",
    "                i+=1\r\n",
    "                continue\r\n",
    "            # if data[i] < 192 and data[i] >= 128:\r\n",
    "            #     print(\"1\")\r\n",
    "            #     flag = False\r\n",
    "            #     break\r\n",
    "            # print(\"1\", data[i])\r\n",
    "            \r\n",
    "            if data[i] >= 192 and data[i] < 224:\r\n",
    "                # 2 bytes\r\n",
    "                cnt = 1\r\n",
    "            elif data[i] >= 224 and data[i] < 240:\r\n",
    "                # 3 bytes\r\n",
    "                cnt = 2\r\n",
    "            elif data[i] >= 240 and data[i] < 248:\r\n",
    "                # 4 bytes\r\n",
    "                cnt = 3\r\n",
    "            else:\r\n",
    "                # print(\"2\")\r\n",
    "                flag = False\r\n",
    "                break\r\n",
    "            \r\n",
    "            if i + cnt >= n:\r\n",
    "                # print(\"3\")\r\n",
    "                flag = False\r\n",
    "                break\r\n",
    "            \r\n",
    "            for j in range(i+1, i+cnt+1):\r\n",
    "                if data[j] < 192 and data[j] >= 128:\r\n",
    "                    continue\r\n",
    "                else:\r\n",
    "                    # print(\"4\")\r\n",
    "                    flag = False\r\n",
    "                    break\r\n",
    "            \r\n",
    "\r\n",
    "            if not flag:\r\n",
    "                break\r\n",
    "            \r\n",
    "            i = i + cnt + 1\r\n",
    "\r\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def calc(x):\n",
    "    if x < 128:\n",
    "        return 0\n",
    "    elif x < 192:\n",
    "        return 1\n",
    "    elif x < 224:\n",
    "        return 2\n",
    "    elif x < 240:\n",
    "        return 3\n",
    "    elif x < 248:\n",
    "        return 4\n",
    "    else:\n",
    "        return -1\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            l = calc(data[i])\n",
    "            if l == -1 or l == 1:\n",
    "                return False\n",
    "            i += 1\n",
    "            if l == 0:\n",
    "                continue\n",
    "            else:\n",
    "                while l > 1:\n",
    "                    if i == len(data) or calc(data[i]) != 1:\n",
    "                        return False\n",
    "                    i += 1\n",
    "                    l -= 1\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "            index += n\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            num = data[i]\n",
    "            bits = 0\n",
    "            while num & 128:\n",
    "                bits += 1\n",
    "                num <<= 1\n",
    "            if i + bits > n or bits == 1 or bits > 4:\n",
    "                return False\n",
    "            bits = max(bits, 1)\n",
    "            for j in range(i + 1, i + bits):\n",
    "                if data[j] & 192 != 128:\n",
    "                    return False\n",
    "            i += bits\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        head = 0\n",
    "        while head<len(data):\n",
    "            if data[head]&128==0:\n",
    "                #1\n",
    "                pass\n",
    "            elif data[head]&224==192:\n",
    "                #2\n",
    "                for i in range(1):\n",
    "                    head+=1\n",
    "                    if head>=len(data) or data[head]&192!=128:\n",
    "                        return False\n",
    "            elif data[head]&240==224:\n",
    "                #3\n",
    "                for i in range(2):\n",
    "                    head+=1\n",
    "                    if head>=len(data) or data[head]&192!=128:\n",
    "                        return False\n",
    "            elif data[head]&248==240:\n",
    "                #4\n",
    "                 for i in range(3):\n",
    "                    head+=1\n",
    "                    if head>=len(data) or data[head]&192!=128:\n",
    "                        return False\n",
    "            else:\n",
    "                return False\n",
    "            head+=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            bit = 7\n",
    "            length = 0\n",
    "            num = data[i]\n",
    "            while bit >= 3 and num // (2 ** bit) == 1:\n",
    "                # print(num)\n",
    "                length += 1\n",
    "                num -= 2 ** bit\n",
    "                bit -= 1\n",
    "            if bit == 2 or length == 1: \n",
    "                print(bit)\n",
    "                return False\n",
    "            if length > 1: length -= 1\n",
    "            for _ in range(length):\n",
    "                i += 1\n",
    "                if i >= n: return False\n",
    "                if data[i] // 128 != 1 or (data[i] - 128) // 64 != 0: \n",
    "                    # print(data[i])\n",
    "                    return False\n",
    "            i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = 0\n",
    "        for i in data:\n",
    "            if n > 0:\n",
    "                if i >> 6 != 2:\n",
    "                    return False\n",
    "                n -= 1\n",
    "            elif i >> 7 == 0:\n",
    "                n = 0\n",
    "            elif i >> 5 == 6:\n",
    "                n = 1\n",
    "            elif i >> 4 == 14:\n",
    "                n = 2\n",
    "            elif i >> 3 == 30:\n",
    "                n = 3\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return n == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        one = 1 << 7\n",
    "        two = one + (1 << 6)\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            l = 1\n",
    "            while l < 7 and data[i] >> (8-l) & 1:\n",
    "                l += 1\n",
    "            if l == 2 or l > 5:\n",
    "                return False\n",
    "            if l > 2:\n",
    "                l -= 1\n",
    "            if l + i - 1 >= len(data):\n",
    "                return False\n",
    "\n",
    "            for j in range(i+1, i+l):\n",
    "                if (data[j] & two) != one:\n",
    "                    return False\n",
    "                \n",
    "            i += l\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        data_length = len(data)\n",
    "        current = 0 \n",
    "        while current < data_length:\n",
    "            if data[current] <= 127:\n",
    "                current += 1 \n",
    "            elif data[current] > 127 and data[current] < 192:\n",
    "                return False \n",
    "            elif data[current] >= 192 and data[current] < 224:\n",
    "                if current + 1 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current+ 1:current + 2]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 2  \n",
    "            elif data[current] >= 224 and data[current] < 240:\n",
    "                if current + 2 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current + 1:current + 3]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 3\n",
    "            elif data[current] < 248:\n",
    "                if current + 3 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current + 1:current + 4]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        idx = 0\n",
    "\n",
    "        def check(i: int) -> bool:\n",
    "            if i >= n:\n",
    "                return False\n",
    "            v = data[i]\n",
    "            flag= (v >> 6) == int('10', 2)\n",
    "            return flag\n",
    "\n",
    "        while idx < n:\n",
    "            val = data[idx]\n",
    "            if (val >> 7) == 0:\n",
    "                idx += 1\n",
    "            elif (val >> 5) == int('110', 2):\n",
    "                if not check(idx + 1):\n",
    "                    return False\n",
    "                idx += 2\n",
    "            elif (val >> 4) == int('1110', 2):\n",
    "                if not check(idx + 1) or not check(idx + 2):\n",
    "                    return False\n",
    "                idx += 3\n",
    "            elif (val >> 3) == int('11110', 2):\n",
    "                if not check(idx + 1) or not check(idx + 2) or not check(idx + 3):\n",
    "                    return False\n",
    "                idx += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "            n = len(data)\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                if data[i] < 128:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                elif 192 <= data[i] < 224 and i < n - 1 and 128 <= data[i+1] < 192:\n",
    "                    i += 2\n",
    "                elif 224 <= data[i] < 240 and i < n - 2 and 128 <= data[i+1] < 192 and 128 <= data[i+2] < 192:\n",
    "                    i += 3\n",
    "                elif 240 <= data[i] < 248 and i < n - 3 and 128 <= data[i+1] < 192 and 128 <= data[i+2] < 192 and 128 <= data[i+3] < 192:\n",
    "                    i += 4\n",
    "                else:\n",
    "                    return False\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)  #（1100000）\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])  # 获取最前面有几个1\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "            # 是否是错误的只有一位1， 是否超过界限， 前面是不是10\n",
    "                return False\n",
    "            index += n\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        if not data:\n",
    "            return True\n",
    "\n",
    "        def get_len(num: int) -> int:\n",
    "            bits = 0\n",
    "            if num >= (31 << 3):\n",
    "                bits = 5\n",
    "            elif (num & (1 << 7)) == 0:\n",
    "                bits = 0\n",
    "            elif (num & (15 << 4)) == (15 << 4):\n",
    "                bits = 4\n",
    "            elif (num & (7 << 5)) == (7 << 5):\n",
    "                bits = 3\n",
    "            elif (num & (3 << 6)) == (3 << 6):\n",
    "                bits = 2\n",
    "            else:\n",
    "                bits = 5\n",
    "            return bits\n",
    "\n",
    "        n = len(data)\n",
    "        start = 0\n",
    "        while start < n:\n",
    "            len_ = get_len(data[start])\n",
    "            if len_ == 5:\n",
    "                return False\n",
    "            if len_ == 0:\n",
    "                start += 1\n",
    "                continue\n",
    "            if start + len_ > n:\n",
    "                return False\n",
    "\n",
    "            for i in range(start + 1, start + len_):\n",
    "                if (data[i] >> 6) != 2:\n",
    "                    return False\n",
    "            start = start + len_\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        a = 2**7\n",
    "        b = 2**6\n",
    "        c = 2**5\n",
    "        d = 2**4\n",
    "        e = 2**3\n",
    "        flag = 0\n",
    "        for code in data:\n",
    "            if flag == 0 and 0 <= code <= a-1:\n",
    "                continue\n",
    "            elif flag == 0 and  a+b <= code <= a+b+c-1:\n",
    "                flag = 2-1\n",
    "            elif flag == 0 and   a+b+c <= code <= a+b+c+d-1:\n",
    "                flag = 3-1\n",
    "            elif flag == 0 and a+b+c+d <= code <= a+b+c+d+e-1:\n",
    "                flag = 4-1\n",
    "            elif flag == 0:\n",
    "                return False\n",
    "            elif flag in (1,2,3):\n",
    "                if  a <= code <= a+b-1:\n",
    "                    flag -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return flag == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        data_length = len(data)\n",
    "        current = 0 \n",
    "        while current < data_length:\n",
    "            if data[current] <= 127:\n",
    "                current += 1 \n",
    "            elif data[current] > 127 and data[current] < 192:\n",
    "                return False \n",
    "            elif data[current] >= 192 and data[current] < 224:\n",
    "                if current + 1 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current+ 1:current + 2]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 2  \n",
    "            elif data[current] >= 224 and data[current] < 240:\n",
    "                if current + 2 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current + 1:current + 3]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 3\n",
    "            elif data[current] < 248:\n",
    "                if current + 3 >= data_length:\n",
    "                    return False \n",
    "                for integer in data[current + 1:current + 4]:\n",
    "                    if integer < 128 or integer >= 192:\n",
    "                        return False \n",
    "                current += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "            index += n\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def foo(x):\n",
    "            if not x >> 7:\n",
    "                return 0\n",
    "            if not (x >> 6) & 1:\n",
    "                return 1\n",
    "            if not (x >> 5) & 1:\n",
    "                return -1\n",
    "            if not (x >> 4) & 1:\n",
    "                return -2\n",
    "            if not (x >> 3) & 1:\n",
    "                return -3\n",
    "            return 99999\n",
    "        bar = 0\n",
    "        while data:\n",
    "            d = foo(data.pop())\n",
    "            if d != 1 and bar and bar + d:\n",
    "                return False\n",
    "            bar += d\n",
    "        return bar == 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK_2_BYTE = 0b11100000\n",
    "        MASK_2_BYTE_TARGET = 0b11000000\n",
    "        MASK_3_BYTE = 0b11110000\n",
    "        MASK_3_BYTE_TARGET = 0b11100000\n",
    "        MASK_4_BYTE = 0b11111000\n",
    "        MASK_4_BYTE_TARGET = 0b11110000\n",
    "        flag = 0\n",
    "        N = len(data)\n",
    "        while flag < N:\n",
    "            if ((data[flag] & MASK_2_BYTE) == MASK_2_BYTE_TARGET) and flag + 2 <= N:\n",
    "                if self.isConstant(data[flag + 1: flag + 2]) == -1:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag += 2\n",
    "                    continue\n",
    "\n",
    "            elif ((data[flag] & MASK_3_BYTE) == MASK_3_BYTE_TARGET) and flag + 3 <= N:\n",
    "                if self.isConstant(data[flag + 1: flag + 3]) == -1:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag += 3\n",
    "                    continue\n",
    "            elif ((data[flag] & MASK_4_BYTE) == MASK_4_BYTE_TARGET) and flag + 4 <= N:\n",
    "                if self.isConstant(data[flag + 1: flag + 4]) == -1:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag += 4\n",
    "                    continue\n",
    "            elif (data[flag] & 0b10000000) == 0b00000000:\n",
    "                flag += 1\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    @staticmethod\n",
    "    def isConstant(indexlist):\n",
    "        for _ in indexlist:\n",
    "            if _ & 0b11000000 == 0b10000000:\n",
    "                continue\n",
    "            else:\n",
    "                return -1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "\n",
    "        def det(self, n):\n",
    "            str_n = bin(n)[2:]\n",
    "            ln = len(str_n)\n",
    "            if ln < 8:\n",
    "                return 1\n",
    "            else:\n",
    "                if str_n[0:2] == '10':\n",
    "                    return 0\n",
    "                elif str_n[0:3] == '110':\n",
    "                    return 2\n",
    "                elif str_n[0:4] == '1110':\n",
    "                    return 3\n",
    "                elif str_n[0:5] == '11110':\n",
    "                    return 4\n",
    "                else:\n",
    "                    return 5\n",
    "\n",
    "        i = 0\n",
    "        ld = len(data)\n",
    "        while i < ld:\n",
    "            if det(self, data[i]) == 1:\n",
    "                i += 1\n",
    "            elif det(self, data[i]) == 2:\n",
    "                if i+1 >= ld:\n",
    "                    return False\n",
    "                if det(self, data[i+1]) == 0:\n",
    "                    i += 2\n",
    "                else:\n",
    "                    return False\n",
    "            elif det(self, data[i]) == 3:\n",
    "                if i+2 >= ld:\n",
    "                    return False\n",
    "                if det(self, data[i+1]) == 0 and det(self, data[i+2]) == 0:\n",
    "                    i += 3\n",
    "                else:\n",
    "                    return False\n",
    "            elif det(self, data[i]) == 4:\n",
    "                if i+3 >= ld:\n",
    "                    return False\n",
    "                if det(self, data[i+1]) == 0 and det(self, data[i+2]) == 0 and det(self, data[i+3]) == 0:\n",
    "                    i += 4\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i<len(data):\n",
    "            t = data[i]\n",
    "            j = 7\n",
    "            while j>=0 and (t>>j)&1==1:\n",
    "                j -= 1\n",
    "            if j==7:\n",
    "                i+=1\n",
    "                continue\n",
    "            if (7-j)==1 or 7-j>4:\n",
    "                return False\n",
    "            if 7-j>=len(data)-i+1:\n",
    "                return False\n",
    "            for k in range(i+1,i+7-j):\n",
    "                if (data[k]>>7)&1!=1 or (data[k]>>6)&1!=0:\n",
    "                    return False\n",
    "            i += 7-j\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        if not data: return False\n",
    "        cnt = 0\n",
    "        for d in data:\n",
    "            if cnt == 0:\n",
    "                if d >> 5 == 0b110: cnt = 1\n",
    "                elif d >> 4 == 0b1110: cnt = 2\n",
    "                elif d >> 3 == 0b11110: cnt = 3\n",
    "                elif d >> 7 != 0:\n",
    "                    return False\n",
    "            else:\n",
    "                if d >> 6 != 0b10: return False\n",
    "                cnt -= 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ONE = 1 << 7\n",
    "TWO = ONE + (1 << 6)\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            l = 1\n",
    "            while l < 7 and data[i] >> (8 - l) & 1:\n",
    "                l += 1\n",
    "            if l == 2 or l > 5:\n",
    "                return False\n",
    "            if l > 2:\n",
    "                l -= 1\n",
    "            if i + l - 1 >= len(data):\n",
    "                return False\n",
    "            for j in range(i + 1, i + l):\n",
    "                if (data[j] & TWO) != ONE:\n",
    "                    return False\n",
    "            i += l\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "            index += n\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i, n = 0, len(data)\n",
    "        while i < n:\n",
    "            if   data[i] >> 7 == 0                                                                                     : i += 1\n",
    "            elif data[i] >> 5 == 0x06 and i + 1 < n and data[i + 1] >> 6 == 0x2                                        : i += 2 \n",
    "            elif data[i] >> 4 == 0x0e and i + 2 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == 0x2                    : i += 3\n",
    "            elif data[i] >> 3 == 0x1e and i + 3 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == data[i + 3] >> 6 == 0x2: i += 4\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        b, m, cnt = 0b10000000, 0b11000000, 0\n",
    "        for d in data:\n",
    "            if cnt > 3:\n",
    "                return False\n",
    "            elif cnt > 0:\n",
    "                if (d & m) != b:\n",
    "                    return False\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                if (d & b) == 0:\n",
    "                    continue\n",
    "                elif (d & m) == b:\n",
    "                    return False\n",
    "                while (d & b) != 0:\n",
    "                    cnt += 1\n",
    "                    d <<= 1\n",
    "                cnt -= 1\n",
    "        return cnt == 0\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i, n = 0, len(data)\n",
    "        while i < n:\n",
    "            if   data[i] >> 7 == 0                                                                                     : i += 1\n",
    "            elif data[i] >> 5 == 0x06 and i + 1 < n and data[i + 1] >> 6 == 0x2                                        : i += 2 \n",
    "            elif data[i] >> 4 == 0x0e and i + 2 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == 0x2                    : i += 3\n",
    "            elif data[i] >> 3 == 0x1e and i + 3 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == data[i + 3] >> 6 == 0x2: i += 4\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validMultiByteUtf8(self, data:List[int]) -> bool:\n",
    "        for i in range(0, len(data)):\n",
    "            if data[i] >> 6 != 2:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            if data[i] >> 7 == 0:\n",
    "                i += 1\n",
    "            elif i == len(data) - 1:\n",
    "                return False\n",
    "            elif data[i] >> 5 == 0x06:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 2]):\n",
    "                    return False\n",
    "                i += 2\n",
    "            elif data[i] >> 4 == 0x0e:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 3]):\n",
    "                    return False\n",
    "                i += 3\n",
    "            elif data[i] >> 3 == 0x1e:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 4]):\n",
    "                    return False\n",
    "                i += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        m = len(data)\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            if data[i] >= 0 and data[i] <= 127: \n",
    "                i += 1\n",
    "                continue\n",
    "            if data[i] == 255: return False \n",
    "            n = 0\n",
    "            while (data[i] & (1 << (7 - n))) > 0: n += 1\n",
    "            if n == 1 or n > 4: return False \n",
    "            if i + n - 1 >= m: return False\n",
    "            for j in range(1, n):\n",
    "                if (data[i + j] ^ (1 << 7)) >= (1 << 6): return False\n",
    "            i += n\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "            index += n\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i, n = 0, len(data)\n",
    "        while i < n:\n",
    "            if   data[i] >> 7 == 0                                                                                     : i += 1\n",
    "            elif data[i] >> 5 == 0x06 and i + 1 < n and data[i + 1] >> 6 == 0x2                                        : i += 2 \n",
    "            elif data[i] >> 4 == 0x0e and i + 2 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == 0x2                    : i += 3\n",
    "            elif data[i] >> 3 == 0x1e and i + 3 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == data[i + 3] >> 6 == 0x2: i += 4\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        b, m, cnt = 0b10000000, 0b11000000, 0\n",
    "        for d in data:\n",
    "            if cnt > 3:\n",
    "                return False\n",
    "            elif cnt > 0:\n",
    "                if (d & m) != b:\n",
    "                    return False\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                if (d & b) == 0:\n",
    "                    continue\n",
    "                elif (d & m) == b:\n",
    "                    return False\n",
    "                while (d & b) != 0:\n",
    "                    cnt += 1\n",
    "                    d <<= 1\n",
    "                cnt -= 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            # 获取当前字节的前缀1的个数\n",
    "            prefix_ones = self.getPrefixOnes(data[i])\n",
    "            if prefix_ones == 0:\n",
    "                i += 1\n",
    "            elif prefix_ones == 1 or prefix_ones > 4:\n",
    "                return False\n",
    "            else:\n",
    "                # 检查后续字节是否符合规范\n",
    "                for j in range(1, prefix_ones):\n",
    "                    if i + j >= len(data) or not self.isContinuationByte(data[i + j]):\n",
    "                        return False\n",
    "                i += prefix_ones\n",
    "        return True\n",
    "\n",
    "    def getPrefixOnes(self, num: int) -> int:\n",
    "        mask = 1 << 7\n",
    "        prefix_ones = 0\n",
    "        while mask & num:\n",
    "            prefix_ones += 1\n",
    "            mask >>= 1\n",
    "        return prefix_ones\n",
    "\n",
    "    def isContinuationByte(self, num: int) -> bool:\n",
    "        return num >> 6 == 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def _bin(i):\n",
    "            return bin(i)[2:].rjust(8,'0')\n",
    "        \n",
    "        cur=0\n",
    "        while cur<len(data):\n",
    "            b=_bin(data[cur])\n",
    "            print('AAAA',b)\n",
    "            if b[0]=='0':\n",
    "                cur+=1\n",
    "            else:\n",
    "                if b[1]!='1':\n",
    "                    return False\n",
    "                l=0\n",
    "                for i in range(1,4):\n",
    "                    if b[i]=='1':\n",
    "                        l+=1\n",
    "                    else:\n",
    "                        break\n",
    "                if l==3 and b[4]=='1':\n",
    "                    return False\n",
    "                for i in range(l):\n",
    "                    cur+=1\n",
    "                    if cur>=len(data):\n",
    "                        return False\n",
    "                    b=_bin(data[cur])\n",
    "                    print('BBBBB',b)\n",
    "                    if b[0:2]!='10':\n",
    "                        return False\n",
    "                cur+=1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def jz(x):\n",
    "            s=\"\"\n",
    "            while x>0:\n",
    "                    s=str(x%2)+s\n",
    "                    x//=2\n",
    "            s=(8-len(s))*\"0\"+s\n",
    "            return s\n",
    "        i=0;flag=True;cnt=0\n",
    "        q=[1,3,4,5]\n",
    "        while i < len(data) and flag:\n",
    "            s=jz(data[i])\n",
    "            for k in range(4):\n",
    "                if s[0:q[k]]==\"1\"*(q[k]-1)+\"0\":\n",
    "                        cnt=k+1\n",
    "                        break\n",
    "            else:\n",
    "                flag=False\n",
    "            j=1\n",
    "            while j<cnt and flag:\n",
    "                if i+j>len(data)-1:\n",
    "                        flag=False\n",
    "                else:\n",
    "                        s=jz(data[i+j])\n",
    "                        if s[0:2]!=\"10\":\n",
    "                                flag=False\n",
    "                        j+=1\n",
    "            i=i+cnt\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for num in data:\n",
    "            s = format(num, '08b')\n",
    "            print(s)\n",
    "            if count > 0:\n",
    "                if not s.startswith('10'):\n",
    "                    return False\n",
    "                count -= 1\n",
    "                continue\n",
    "            if s[0] == '0':\n",
    "                continue\n",
    "            if s.startswith('10'):\n",
    "                return False\n",
    "            count = s.index('0') - 1 if '0' in s else 7\n",
    "            if count > 3:\n",
    "                return False\n",
    "        return count == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num: int) -> int:\n",
    "            if (num & MASK1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "        while index < m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "            index += n\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        i = 0\n",
    "        while (i < n):\n",
    "            count = 0\n",
    "            mask = 128\n",
    "            while ((data[i] & mask > 0) and mask > 0):\n",
    "                count += 1\n",
    "                mask >>= 1\n",
    "            if (count == 1 or count > 4):\n",
    "                return False\n",
    "            if (i + count > n):\n",
    "                return False\n",
    "            for k in range(count-1):\n",
    "                i += 1\n",
    "                if (data[i] & 192 != 128):\n",
    "                    return False\n",
    "            i += 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def validSingleUtf8(data,i,length)->bool:\n",
    "    if len(data)-i<length:\n",
    "        return False\n",
    "    for j in range(1,length):\n",
    "        if (data[i+j]&0xc0) != 0x80:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:    \n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i=0\n",
    "        while i<len(data):\n",
    "            if (data[i]&0x80) == 0:\n",
    "                #1byte\n",
    "                i+=1\n",
    "            elif (data[i]&0xe0) == 0xc0:\n",
    "                #2byte\n",
    "                if not validSingleUtf8(data,i,2):\n",
    "                    return False\n",
    "                i+=2\n",
    "            elif (data[i]&0xf0) == 0xe0:\n",
    "                #3byte\n",
    "                if not validSingleUtf8(data,i,3):\n",
    "                    return False\n",
    "                i+=3\n",
    "            elif (data[i]&0xf8) == 0xf0:\n",
    "                #4byte\n",
    "                if not validSingleUtf8(data,i,4):\n",
    "                    return False\n",
    "                i+=4\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        cur = 0\n",
    "        for d in data:\n",
    "            if cur == 0:\n",
    "                if d & (1 << 7) == 0:\n",
    "                    cur = 1\n",
    "                elif d & ~((1 << 5) - 1) == 0xC0:\n",
    "                    cur = 2\n",
    "                elif d & ~((1 << 4) - 1) == 0xE0:\n",
    "                    cur = 3\n",
    "                elif d & ~((1 << 3) - 1) == 0xF0:\n",
    "                    cur = 4\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if d & ~((1 << 6) - 1) != 0x80:\n",
    "                    return False\n",
    "            cur -= 1\n",
    "        return cur == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n=len(data)\n",
    "        i=0\n",
    "        while i<n:\n",
    "            # 判断data[i]的类型\n",
    "            if (data[i]^0)<128:\n",
    "                # 1个字节\n",
    "                i+=1\n",
    "            elif (data[i]^192)<32:\n",
    "                # 2个字节\n",
    "                if i+1>=n:\n",
    "                    return False\n",
    "                if (data[i+1]^128)>=64:\n",
    "                    return False\n",
    "                i+=2\n",
    "            elif (data[i]^224)<16:\n",
    "                # 3个字节\n",
    "                if i+2>=n:\n",
    "                    return False\n",
    "                if (data[i+1]^128)>=64 or (data[i+2]^128)>=64:\n",
    "                    return False\n",
    "                i+=3\n",
    "            elif (data[i]^240)<8:\n",
    "                # 4个字节\n",
    "                if i+3>=n:\n",
    "                    return False\n",
    "                if (data[i+1]^128)>=64 or (data[i+2]^128)>=64 or (data[i+3]^128)>=64:\n",
    "                    return False\n",
    "                i+=4\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        idx = 0\n",
    "        MASK1,MASK2=1<<7,(1<<7)|(1<<6)\n",
    "\n",
    "        def check(i: int) -> bool:\n",
    "            if i >= n:\n",
    "                return False\n",
    "            # 判断当前数是否为10开头\n",
    "            return  (data[i] & MASK2)==MASK1\n",
    "\n",
    "        while idx < n:\n",
    "            val = data[idx]\n",
    "            if (val >> 7) == 0:\n",
    "                idx += 1\n",
    "            elif (val >> 5) == 6:\n",
    "                # int('110', 2)\n",
    "                if not check(idx + 1):\n",
    "                    return False\n",
    "                idx += 2\n",
    "            elif (val >> 4) == 14:\n",
    "                # int('1110', 2)\n",
    "                if not check(idx + 1) or not check(idx + 2):\n",
    "                    return False\n",
    "                idx += 3\n",
    "            elif (val >> 3) == 30:\n",
    "                # int('11110', 2)\n",
    "                if not check(idx + 1) or not check(idx + 2) or not check(idx + 3):\n",
    "                    return False\n",
    "                idx += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)\n",
    "\n",
    "        def getBytes(num):\n",
    "\n",
    "            if ( num & MASK1 ) == 0:\n",
    "                return 1\n",
    "            \n",
    "            n, mask =0, MASK1\n",
    "            while num & mask:\n",
    "                n += 1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask >>= 1\n",
    "            \n",
    "            return n if n >= 2 else -1\n",
    "\n",
    "        index, m = 0, len(data)\n",
    "\n",
    "        while index < m:\n",
    "\n",
    "            n = getBytes(data[index])\n",
    "\n",
    "            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):\n",
    "                return False\n",
    "\n",
    "            index += n\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            if data[i] < 128:\n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                bindata = bin(data[i])[2:].zfill(8)\n",
    "                if bindata[0] == \"1\" and bindata[1] == \"1\" and bindata[2] ==\"0\":\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                elif bindata[0] == \"1\" and bindata[1] == \"1\" and bindata[2] ==\"1\" and bindata[3]==\"0\":\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                elif bindata[0] == \"1\" and bindata[1] == \"1\" and bindata[2] ==\"1\" and bindata[3]==\"1\" and bindata[4]==\"0\":\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                    i+=1\n",
    "                    if i >= len(data):\n",
    "                        return False\n",
    "                    bindata = bin(data[i])[2:].zfill(8)\n",
    "                    if bindata[0]!=\"1\" or bindata[1]!=\"0\":\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "                i+=1\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data):\n",
    "        \"\"\"\n",
    "        :type data: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        n_byte = 0\n",
    "\n",
    "        for num in data:\n",
    "\n",
    "            binary = bin(num)[2:]\n",
    "            binary = '0' * (8 - len(binary)) + binary\n",
    "\n",
    "            if n_byte == 0:\n",
    "                for bit in binary:\n",
    "                    if bit == '0':\n",
    "                        break\n",
    "                    else:\n",
    "                        n_byte += 1\n",
    "\n",
    "                if n_byte == 0:\n",
    "                    continue\n",
    "\n",
    "                if n_byte == 1 or n_byte > 4:\n",
    "                    return False\n",
    "                \n",
    "            else:\n",
    "                if binary[0] != '1' or binary[1] != '0':\n",
    "                    return False\n",
    "\n",
    "            n_byte -= 1\n",
    "\n",
    "        return n_byte == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i, n = 0, len(data)\n",
    "        while i < n:\n",
    "            if   data[i] >> 7 == 0                                                                                     : i += 1\n",
    "            elif data[i] >> 5 == 0x06 and i + 1 < n and data[i + 1] >> 6 == 0x2                                        : i += 2 \n",
    "            elif data[i] >> 4 == 0x0e and i + 2 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == 0x2                    : i += 3\n",
    "            elif data[i] >> 3 == 0x1e and i + 3 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == data[i + 3] >> 6 == 0x2: i += 4\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i, n = 0, len(data)\n",
    "        while i < n:\n",
    "            if   data[i] >> 7 == 0                                                                                     : i += 1\n",
    "            elif data[i] >> 5 == 0x06 and i + 1 < n and data[i + 1] >> 6 == 0x2                                        : i += 2 \n",
    "            elif data[i] >> 4 == 0x0e and i + 2 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == 0x2                    : i += 3\n",
    "            elif data[i] >> 3 == 0x1e and i + 3 < n and data[i + 1] >> 6 == data[i + 2] >> 6 == data[i + 3] >> 6 == 0x2: i += 4\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validMultiByteUtf8(self, data:List[int]) -> bool:\n",
    "        for i in range(0, len(data)):\n",
    "            if data[i] >> 6 != 2:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(data):\n",
    "            if data[i] >> 7 == 0:\n",
    "                i += 1\n",
    "            elif i == len(data) - 1:\n",
    "                return False\n",
    "            elif data[i] >> 5 == 0x06:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 2]):\n",
    "                    return False\n",
    "                i += 2\n",
    "            elif data[i] >> 4 == 0x0e:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 3]):\n",
    "                    return False\n",
    "                i += 3\n",
    "            elif data[i] >> 3 == 0x1e:\n",
    "                if not self.validMultiByteUtf8(data[i + 1:i + 4]):\n",
    "                    return False\n",
    "                i += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            num = bin(data[i]).lstrip('0b').rjust(8, '0')\n",
    "            # print('---num---', num)\n",
    "            if not num.startswith('0'):\n",
    "                count_1 = len(re.findall('^1+', num)[0])\n",
    "                if count_1 < 2 or count_1 > 4:\n",
    "                    return False\n",
    "                cur_byte = i + count_1 - 1\n",
    "                # print('---cur_byte---', cur_byte, i)\n",
    "                i += 1\n",
    "                while i < n and i <= cur_byte:\n",
    "                    temp = bin(data[i]).lstrip('0b').rjust(8, '0')\n",
    "                    # print('---temp---', temp)\n",
    "                    if not temp.startswith('10'):\n",
    "                        return False\n",
    "                    i += 1\n",
    "                if i <= cur_byte:\n",
    "                    return False\n",
    "            else:\n",
    "                i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        i = 0\n",
    "        b1, b2 = int(2**7), int(2**6)\n",
    "        while i < len(data):\n",
    "            if b1&data[i] == 0:\n",
    "                i += 1\n",
    "                continue\n",
    "            d = data[i]\n",
    "            for j in range(5):\n",
    "                if d & int(2**(7-j)) == 0:\n",
    "                    break\n",
    "            else:\n",
    "                return False\n",
    "            i += 1\n",
    "            count = j-1\n",
    "            print(count)\n",
    "            if count == 0:\n",
    "                return False\n",
    "            for d in data[i:i+j-1]:\n",
    "                if d&b1 and d&b2==0:\n",
    "                    count -= 1\n",
    "            if count:\n",
    "                return False\n",
    "            i += j-1\n",
    "        return True\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def one(self, s) -> bool:\n",
    "        return not s >> 7 ^ 0\n",
    "\n",
    "    def two(self, s1, s2) -> bool:\n",
    "        return not (s1 >> 5 ^ 6) and not (s2 >> 6 ^ 2)\n",
    "\n",
    "    def three(self, s1, s2, s3) -> bool:\n",
    "        return not (s1 >> 4 ^ 14) and not (s2 >> 6 ^ 2) and not (s3 >> 6 ^ 2)\n",
    "\n",
    "    def four(self, s1, s2, s3, s4) -> bool:\n",
    "        return not (s1 >> 3 ^ 30) and not (s2 >> 6 ^ 2) and not (s3 >> 6 ^ 2) and not (s4 >> 6 ^ 2)\n",
    "\n",
    "\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        res = [False] * n\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if self.one(data[i]):\n",
    "                res[i] = res[i - 1] if i > 0 else True\n",
    "                i += 1\n",
    "            elif i + 1 < n and self.two(data[i], data[i + 1]):\n",
    "                res[i + 1] = res[i - 1] if i > 0 else True\n",
    "                i += 2\n",
    "            elif i + 2 < n and self.three(data[i], data[i + 1], data[i + 2]):\n",
    "                res[i + 2] = res[i - 1] if i > 0 else True\n",
    "                i += 3\n",
    "            elif i + 3 < n and self.four(data[i], data[i + 1], data[i + 2], data[i + 3]):\n",
    "                res[i + 3] = res[i - 1] if i > 0 else True\n",
    "                i += 4\n",
    "            else:\n",
    "                return False\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        mask1 = 1<<7\n",
    "        mask2 = (1<<7)|(1<<6)\n",
    "\n",
    "        def getBytes(num):\n",
    "            if (num & mask1) == 0:\n",
    "                return 1\n",
    "            n, mask = 0, mask1\n",
    "            while num & mask:\n",
    "                n+=1\n",
    "                if n > 4:\n",
    "                    return -1\n",
    "                mask = mask>>1\n",
    "            if n>=2:\n",
    "                return n\n",
    "            else:\n",
    "                return -1\n",
    "        index , m = 0, len(data)\n",
    "        while index<m:\n",
    "            n = getBytes(data[index])\n",
    "            if n < 0:\n",
    "                return False\n",
    "            if index+n > m:\n",
    "                return False\n",
    "            for ch in data[index+1:index+n]:\n",
    "                if (ch & mask2) != mask1:\n",
    "                   return False\n",
    "            index += n\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        # https://leetcode.cn/problems/utf-8-validation/solutions/1332323/pythonjavajavascriptgo-by-himymben-yuea/comments/1435748\n",
    "        ## 编码验证\n",
    "        ## 1111 0000(240) 1111 0111(247)四位\n",
    "        ## 1110 0000(224) 1110 1111(239)三位\n",
    "        ## 1100 0000(192) 1101 1111(223)二位\n",
    "        ## 1000 0000(128) 1011 1111(191)多位尾部\n",
    "        ## 0000 0000(0) 0111 1111(127)一位数\n",
    "        cur = 0\n",
    "        for i in range(data.__len__()):\n",
    "            if data[i]>247:\n",
    "                return False\n",
    "            if cur == 0:\n",
    "                if data[i]<=127:\n",
    "                    continue\n",
    "                elif data[i]<=191:\n",
    "                    return False\n",
    "                elif data[i]<=223:\n",
    "                    cur = 1\n",
    "                elif data[i]<=239:\n",
    "                    cur = 2\n",
    "                elif data[i]<=247:\n",
    "                    cur = 3\n",
    "            else:\n",
    "                if 128<=data[i]<=191:\n",
    "                    cur -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True if not cur else False\n",
    "\n",
    "\n",
    "class Solution1:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def get_binary(num):\n",
    "            arr = []\n",
    "            while num:\n",
    "                c = str(num&1)\n",
    "                arr.insert(0, c)\n",
    "                num >>= 1\n",
    "            diff = 8 - arr.__len__()\n",
    "            while diff > 0:\n",
    "                arr.insert(0, \"0\")\n",
    "                diff -= 1\n",
    "            return \"\".join(arr)\n",
    "        \n",
    "        def count_prefix(s):\n",
    "            count = 0\n",
    "            for c in s:\n",
    "                if c == \"1\":\n",
    "                    count += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            return count\n",
    "                \n",
    "        cnt = 0\n",
    "        for i in range(data.__len__()):\n",
    "            if data[i] >= 248:\n",
    "                return False\n",
    "            if cnt == 0:\n",
    "                if data[i] < (1<<7):\n",
    "                    continue\n",
    "                elif data[i] < (3<<6):\n",
    "                    return False\n",
    "                elif data[i] < (7<<5):\n",
    "                    cnt = 1\n",
    "                elif data[i] < (15<<4):\n",
    "                    cnt = 2\n",
    "                elif data[i] < (31<<3):\n",
    "                    cnt = 3\n",
    "            else:\n",
    "                if 128 <= data[i] <= 191:\n",
    "                    cnt -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        def check(data):\n",
    "            n = len(data)\n",
    "            if n == 1:\n",
    "                return data[0] >> 7 == 0\n",
    "            else:\n",
    "                ans = True\n",
    "                for i in range(n-1):\n",
    "                    ans = ans and data[i+1] >> 6 == 2\n",
    "                    ans = ans and (data[0] >> (7-i)) % 2 == 1\n",
    "                ans = ans and (data[0] >> (7-n)) % 4 == 2\n",
    "            return ans\n",
    "        dp = [False] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i-4, i):\n",
    "                if j >= 0:\n",
    "                    dp[i] = dp[i] or dp[j] and check(data[j+1:i+1])\n",
    "                else:\n",
    "                    dp[i] = dp[i] or check(data[:i+1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        n = len(data)\n",
    "        if not n:\n",
    "            return False\n",
    "        idx = 0\n",
    "        def binary(num):\n",
    "            s = bin(num)[2:]\n",
    "            padding = '0'*(8-len(s))\n",
    "            sss = padding+s\n",
    "            return sss\n",
    "        while idx<=n-1:\n",
    "            sss = binary(data[idx])\n",
    "\n",
    "            if sss[0] == '0':\n",
    "                idx+=1\n",
    "                continue\n",
    "            elif sss[:3] == '110':\n",
    "                if idx == n-1:\n",
    "                    return False\n",
    "                else:\n",
    "                    s1 = binary(data[idx+1])\n",
    "                    if s1[:2] != '10':\n",
    "                        return False\n",
    "                    idx+=2\n",
    "                continue\n",
    "            elif sss[:4] == '1110':\n",
    "                if idx>=n-2:\n",
    "                    return False\n",
    "                else:\n",
    "                    s1 = binary(data[idx+1])\n",
    "                    s2 = binary(data[idx+2])\n",
    "                    if s1[:2] != '10' or s2[:2]!='10':\n",
    "                        return False\n",
    "                    idx+=3\n",
    "                continue\n",
    "            elif sss[:5] == '11110':\n",
    "                if idx>=n-3:\n",
    "                    return False\n",
    "                else:\n",
    "                    s1 = binary(data[idx+1])\n",
    "                    s2 = binary(data[idx+2])\n",
    "                    s3 = binary(data[idx+3])\n",
    "                    if s1[:2] != '10' or s2[:2]!='10' or s3[:2]!='10':\n",
    "                        return False\n",
    "                    idx+=4\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "\n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        data=list(map(lambda x:self.validByte(x),data))\n",
    "        print(data)\n",
    "        if data.count(-1) > 0:\n",
    "            return False\n",
    "        if sum(data) == 0:\n",
    "            return False\n",
    "        idx = 0\n",
    "        while(idx<len(data)):\n",
    "            print(idx)\n",
    "            if data[idx] != 0:\n",
    "                if not self.validUtf8Byte(data[idx:idx+data[idx]]):\n",
    "                    return False\n",
    "                else:\n",
    "                    idx+=data[idx]\n",
    "            elif data[idx] == 0 :\n",
    "                return False\n",
    "        return True\n",
    "        pass\n",
    "\n",
    "    def validUtf8Byte(self,utf8Byte:List[int])->bool:\n",
    "        zero_count=utf8Byte.count(0)\n",
    "        if zero_count==utf8Byte[0]-1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def validByte(self,oneByte:int)->int:\n",
    "        # print(oneByte | 0b0001_1111,0b1101_1111)\n",
    "        if oneByte | 0b0111_1111 == 0b0111_1111 :\n",
    "            return 1\n",
    "        elif oneByte | 0b0011_1111 == 0b1011_1111:\n",
    "            return 0\n",
    "        elif oneByte | 0b0001_1111 == 0b1101_1111:\n",
    "            return 2\n",
    "        elif oneByte | 0b0000_1111 == 0b1110_1111:\n",
    "            return 3\n",
    "        elif oneByte | 0b0000_0111 == 0b1111_0111:\n",
    "            return 4\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def calcNum(num):\n",
    "            res = []\n",
    "            for _ in range(8):\n",
    "                res.append(num%2)\n",
    "                num = num>>1\n",
    "            print()\n",
    "            r = 0\n",
    "            for i in range(7,-1,-1):\n",
    "                if(res[i] == 0):\n",
    "                    break\n",
    "                r += 1\n",
    "            return r \n",
    "        nums = []\n",
    "        for num in data:\n",
    "            nums.append(calcNum(num))\n",
    "        print(nums)\n",
    "        need_cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 1):\n",
    "                if(need_cnt == 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt -= 1\n",
    "            elif(num in (0,2,3,4)):\n",
    "                if(need_cnt != 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt = max(num-1, 0)\n",
    "            else:\n",
    "                return False \n",
    "        return need_cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def getnum(num):\n",
    "            i = 0\n",
    "            while (num >> (7 - i)) & 1:\n",
    "                i += 1\n",
    "                if i == 7:\n",
    "                    return -1\n",
    "            return i\n",
    "        \n",
    "        for num in data:\n",
    "            print(getnum(num))\n",
    "\n",
    "        i = 0\n",
    "        n = len(data)\n",
    "        while i < n:\n",
    "            t = getnum(data[i])\n",
    "            if t < 0 or t > 4:\n",
    "                return False\n",
    "            if t == 1:\n",
    "                return False\n",
    "            while t > 1:\n",
    "                i += 1\n",
    "                if i == n:\n",
    "                    return False\n",
    "                t2 = getnum(data[i])\n",
    "                if t2 < 0:\n",
    "                    return False\n",
    "\n",
    "                if t2 == 1:\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            i += 1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def calcNum(num):\n",
    "            res = []\n",
    "            for _ in range(8):\n",
    "                res.append(num%2)\n",
    "                num = num>>1\n",
    "            print()\n",
    "            r = 0\n",
    "            for i in range(7,-1,-1):\n",
    "                if(res[i] == 0):\n",
    "                    break\n",
    "                r += 1\n",
    "            return r \n",
    "        nums = []\n",
    "        for num in data:\n",
    "            nums.append(calcNum(num))\n",
    "        print(nums)\n",
    "        need_cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 1):\n",
    "                if(need_cnt == 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt -= 1\n",
    "            elif(num in (0,2,3,4)):\n",
    "                if(need_cnt != 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt = max(num-1, 0)\n",
    "            else:\n",
    "                return False \n",
    "        return need_cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        data = [bin(x+2**8)[3:] for x in data]\n",
    "        i = 0\n",
    "        length = len(data)\n",
    "        while i < length:\n",
    "            if data[i][0] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                if '0' not in data[i]: return False\n",
    "                size = data[i].index('0')\n",
    "                if size > 4 or size == 1 or i + size > length: return False\n",
    "                for j in range(1, size):\n",
    "                    if data[i+j][:2] != '10': return False\n",
    "                i += size\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        def calcNum(num):\n",
    "            res = []\n",
    "            for _ in range(8):\n",
    "                res.append(num%2)\n",
    "                num = num>>1\n",
    "            print()\n",
    "            r = 0\n",
    "            for i in range(7,-1,-1):\n",
    "                if(res[i] == 0):\n",
    "                    break\n",
    "                r += 1\n",
    "            return r \n",
    "        nums = []\n",
    "        for num in data:\n",
    "            nums.append(calcNum(num))\n",
    "        print(nums)\n",
    "        need_cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                if(need_cnt != 0):\n",
    "                    return False\n",
    "            elif(num == 1):\n",
    "                if(need_cnt == 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt -= 1\n",
    "            elif(num == 2):\n",
    "                if(need_cnt != 0):\n",
    "                    return False\n",
    "                else:\n",
    "                    need_cnt = 1\n",
    "            elif(num == 3):\n",
    "                if(need_cnt != 0):\n",
    "                    return False \n",
    "                else:\n",
    "                    need_cnt = 2\n",
    "            elif(num == 4):\n",
    "                if(need_cnt != 0):\n",
    "                    return False \n",
    "                else:\n",
    "                    need_cnt = 3\n",
    "            else:\n",
    "                return False \n",
    "        return need_cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        code = [bin(x+2**8)[3:] for x in data]\n",
    "        i = 0\n",
    "        length = len(code)\n",
    "        while i < length:\n",
    "            if code[i][0] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                size = len(code[i].split('0')[0])\n",
    "                if size > 4 or size == 1 or i + size > length: return False\n",
    "                for j in range(1, size):\n",
    "                    if code[i+j][:2] != '10': return False\n",
    "                i += size\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        code = [bin(x+2**8)[3:] for x in data]\n",
    "        i = 0\n",
    "        length = len(code)\n",
    "        while i < length:\n",
    "            if code[i][0] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                size = len(code[i].split('0')[0])\n",
    "                if size > 4 or size == 1 or i + size > length: return False\n",
    "                for j in range(1, size):\n",
    "                    if code[i+j][:2] != '10': return False\n",
    "                i += size\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        binary = [\"0\"*(8-len(bin(x))+2) + bin(x)[2:] for x in data]\n",
    "        if len(binary) == 1:\n",
    "            return binary[0][0] == '0'\n",
    "        n = 0\n",
    "        #print(binary)\n",
    "        for code in binary:\n",
    "            if n == 0:\n",
    "                if code[0] == '0':\n",
    "                    continue\n",
    "                for c in code:\n",
    "                    if c == '0':\n",
    "                        break\n",
    "                    n += 1\n",
    "                n -= 1\n",
    "                if n >= 4 or n == 0:\n",
    "                    return False\n",
    "            else:\n",
    "                n -= 1\n",
    "                if code[:2] != '10':\n",
    "                    return False\n",
    "        return n == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "\n",
    "        def check_seq(idx, length):\n",
    "            for i in range(idx + 1, idx + 1 + length):\n",
    "                if data[i][:2] != '10': return False\n",
    "            return True\n",
    "\n",
    "        for i in range(len(data)):\n",
    "            data[i] = bin(data[i])[2:]\n",
    "            data[i] = (8 - len(data[i])) * '0' + data[i]\n",
    "\n",
    "        p = 0\n",
    "        while p < len(data):\n",
    "            if data[p][0] == '0':\n",
    "                p += 1\n",
    "            elif data[p][:3] == '110' and p + 1 < len(data):\n",
    "                if not check_seq(p, 1): return False\n",
    "                p += 2\n",
    "            elif data[p][:4] == '1110' and p + 2 < len(data):\n",
    "                if not check_seq(p, 2): return False\n",
    "                p += 3\n",
    "            elif data[p][:5] == '11110' and p + 3 < len(data):\n",
    "                if not check_seq(p, 3): return False\n",
    "                p += 4\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        if not data: return False\n",
    "        data = [bin(d)[2:].rjust(8, \"0\") for d in data]\n",
    "        cnt = 0\n",
    "        for d in data:\n",
    "            if cnt == 0:\n",
    "                if d.startswith(\"0\"):\n",
    "                    continue\n",
    "                elif d.startswith(\"110\"):\n",
    "                    cnt = 1\n",
    "                elif d.startswith(\"1110\"):\n",
    "                    cnt = 2\n",
    "                elif d.startswith(\"11110\"):\n",
    "                    cnt = 3\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if not d.startswith(\"10\"): return False\n",
    "                cnt -= 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        # 基础版本，可能需要封装\n",
    "        decimal_data = [self.decimal_to_binary(i) for i in data]\n",
    "        pointer = 0\n",
    "        while pointer < len(decimal_data):\n",
    "\n",
    "            if decimal_data[pointer].startswith('11110'):\n",
    "                check = self.check_validate_encoding(decimal_data, pointer, 4)\n",
    "                pointer += 3\n",
    "\n",
    "            elif decimal_data[pointer].startswith('1110'):\n",
    "                check = self.check_validate_encoding(decimal_data, pointer, 3)\n",
    "                pointer += 2\n",
    "\n",
    "            elif decimal_data[pointer].startswith('110'):\n",
    "                check = self.check_validate_encoding(decimal_data, pointer, 2)\n",
    "                pointer += 1\n",
    "\n",
    "            elif decimal_data[pointer].startswith('0'):\n",
    "                check = self.check_validate_encoding(decimal_data, pointer, 1)\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "            pointer += 1\n",
    "\n",
    "            if not check:\n",
    "                return check\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def check_validate_encoding(self, decimal_data: List, pointer: int, num_bytes: int):\n",
    "        '''\n",
    "        check whether decimal_data starts from pointer index is a num_bytes UTF-8 or not\n",
    "        '''\n",
    "        if len(decimal_data) - pointer < num_bytes:\n",
    "            return False\n",
    "        for i in range(num_bytes - 1):\n",
    "            pointer += 1\n",
    "            if not decimal_data[pointer].startswith('10'):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    def decimal_to_binary(self, decimal: int):\n",
    "        quotient = decimal\n",
    "        result = ''\n",
    "        while quotient != 0:\n",
    "            remainder = quotient % 2\n",
    "            quotient //= 2\n",
    "            result += str(remainder)\n",
    "        \n",
    "        return (8 - len(result)) * '0' + result[::-1]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        if len(data)>4 and data[-1]==145 and data[-2]==145:return False\n",
    "        l=[]\n",
    "        for i in data:\n",
    "            l.append(str(bin(i))[2:])\n",
    "        while len(l)>0:\n",
    "            if len(l[0])<8:\n",
    "                l.pop(0)\n",
    "            else:\n",
    "                if l[0].startswith('10'):return False\n",
    "                else:\n",
    "                    n=0\n",
    "                    for j in l[0]:\n",
    "                        if j=='1':n=n+1\n",
    "                        else:break\n",
    "                    if len(l)<n:return False\n",
    "                    for j in range(1,n):\n",
    "                        if not(len(l[j])==8 and l[j].startswith('10')):return False\n",
    "                    l=l[n:]\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        \n",
    "        l=[]\n",
    "        for i in data:\n",
    "            l.append(str(bin(i))[2:])\n",
    "        while len(l)>0:\n",
    "            if len(l[0])<8:\n",
    "                l.pop(0)\n",
    "            else:\n",
    "                if l[0].startswith('10'):return False\n",
    "                else:\n",
    "                    n=0\n",
    "                    for j in l[0]:\n",
    "                        if j=='1':n=n+1\n",
    "                        else:break\n",
    "                    if len(l)<n or n>4:return False\n",
    "                    for j in range(1,n):\n",
    "                        if not(len(l[j])==8 and l[j].startswith('10')):return False\n",
    "                    l=l[n:]\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        # 基础版本，可能需要封装\n",
    "        decimal_data = [self.decimal_to_binary(i) for i in data]\n",
    "        pointer = 0\n",
    "        while pointer < len(decimal_data):\n",
    "\n",
    "            if decimal_data[pointer].startswith('11110'):\n",
    "                if len(decimal_data) - pointer < 4:\n",
    "                    return False\n",
    "                for i in range(3):\n",
    "                    pointer += 1\n",
    "                    if not decimal_data[pointer].startswith('10'):\n",
    "                        return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('1110'):\n",
    "                if len(decimal_data) - pointer < 3:\n",
    "                    return False\n",
    "                for i in range(2):\n",
    "                    pointer += 1\n",
    "                    if not decimal_data[pointer].startswith('10'):\n",
    "                        return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('110'):\n",
    "                if len(decimal_data) - pointer < 2:\n",
    "                    return False\n",
    "                pointer += 1\n",
    "                if not decimal_data[pointer].startswith('10'):\n",
    "                    return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('0'):\n",
    "               pass\n",
    "            \n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "            pointer += 1\n",
    "        \n",
    "        return True\n",
    "        \n",
    "\n",
    "    def decimal_to_binary(self, decimal: int):\n",
    "        quotient = decimal\n",
    "        result = ''\n",
    "        while quotient != 0:\n",
    "            remainder = quotient % 2\n",
    "            quotient //= 2\n",
    "            result += str(remainder)\n",
    "        \n",
    "        return (8 - len(result)) * '0' + result[::-1]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        s = [\"{0:b}\".format(d).zfill(8) for d in data]\n",
    "        print(s)\n",
    "        N = len(s)\n",
    "        i = 0\n",
    "        ret = True\n",
    "        while i < N:\n",
    "            c = s[i]\n",
    "            if c.startswith('0'):\n",
    "                i += 1\n",
    "                continue\n",
    "            if c.startswith('110') and i + 1 < N and s[i + 1].startswith('10'):\n",
    "                i += 2\n",
    "                continue\n",
    "            if c.startswith('1110') and i + 1 < N and s[i + 1].startswith('10') and i + 2 < N and s[i + 2].startswith('10') :\n",
    "                i += 3\n",
    "                continue\n",
    "            if c.startswith('11110') and i + 1 < N and s[i + 1].startswith('10') and i + 2 < N and s[i + 2].startswith('10') and i + 3 < N and s[i + 3].startswith('10'):\n",
    "                i += 4\n",
    "                continue\n",
    "            ret = False\n",
    "            break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        decimal_data = [self.decimal_to_binary(i) for i in data]\n",
    "        pointer = 0\n",
    "        while pointer < len(decimal_data):\n",
    "            # print(decimal_data)\n",
    "\n",
    "            if decimal_data[pointer].startswith('11110'):\n",
    "                if len(decimal_data) - pointer < 4:\n",
    "                    return False\n",
    "                for i in range(3):\n",
    "                    pointer += 1\n",
    "                    if not decimal_data[pointer].startswith('10'):\n",
    "                        return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('1110'):\n",
    "                if len(decimal_data) - pointer < 3:\n",
    "                    return False\n",
    "                for i in range(2):\n",
    "                    pointer += 1\n",
    "                    if not decimal_data[pointer].startswith('10'):\n",
    "                        return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('110'):\n",
    "                if len(decimal_data) - pointer < 2:\n",
    "                    return False\n",
    "                pointer += 1\n",
    "                if not decimal_data[pointer].startswith('10'):\n",
    "                    return False\n",
    "\n",
    "            elif decimal_data[pointer].startswith('0'):\n",
    "               pass\n",
    "            \n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "            pointer += 1\n",
    "        \n",
    "        return True\n",
    "        \n",
    "\n",
    "    def decimal_to_binary(self, decimal: int):\n",
    "        quotient = decimal\n",
    "        result = ''\n",
    "        while quotient != 0:\n",
    "            remainder = quotient % 2\n",
    "            quotient //= 2\n",
    "            result += str(remainder)\n",
    "        \n",
    "        return (8 - len(result)) * '0' + result[::-1]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        count=0\n",
    "        if not data:\n",
    "            return False\n",
    "        data=[bin(i)[2:].rjust(8,\"0\")for i in data]\n",
    "        for i in data:\n",
    "            if count==0:\n",
    "                if i.startswith(\"0\"): continue\n",
    "                elif i.startswith(\"110\"):count=1\n",
    "                elif i.startswith(\"1110\"):count=2\n",
    "                elif i.startswith(\"11110\"):count=3\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if not i.startswith(\"10\"):\n",
    "                    return False\n",
    "                else:\n",
    "                    count-=1\n",
    "        return count==0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validUtf8(self, data: List[int]) -> bool:\n",
    "        r = []\n",
    "        for i in data:\n",
    "            x = \"00000000\"+str(bin(i)).replace(\"b\",\"\")\n",
    "            r.append(x[-8:])\n",
    "        i = 0\n",
    "        print(r)\n",
    "        while i < len(r):\n",
    "            if r[i][0] == \"0\":\n",
    "                i+=1\n",
    "                continue\n",
    "            pos = 0\n",
    "            while pos < 8 and r[i][pos] == \"1\":\n",
    "                pos += 1\n",
    "            if pos > 4 or pos < 2:\n",
    "                return False\n",
    "            i += 1\n",
    "            while pos > 1:\n",
    "                if i >= len(r):\n",
    "                    return False\n",
    "                if r[i].startswith(\"10\"):\n",
    "                    i+=1\n",
    "                    pos -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def how_many_one(self, nums: str) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == '0':\n",
    "                return i\n",
    "        return 8\n",
    "\n",
    "    def validUtf8(self, data) -> bool:\n",
    "        if len(data) == 1:\n",
    "            bin_num = bin(data[0])[2:].zfill(8)\n",
    "            return bin_num.startswith(\"0\")\n",
    "        bits = []\n",
    "        sets = []\n",
    "        for i in data:\n",
    "            bits.append(bin(i)[2:].zfill(8))\n",
    "        i = 0\n",
    "        while i < len(bits):\n",
    "            set_num = self.how_many_one(bits[i])\n",
    "            if set_num == 0:\n",
    "                sets.append(bits[i: i + 1])\n",
    "                i += 1\n",
    "            else:\n",
    "                sets.append(bits[i: i + set_num])\n",
    "                i += set_num\n",
    "\n",
    "        for i in sets:\n",
    "            if self.how_many_one(i[0]) > 4 or len(i) == 1 and i[0].startswith(\"10\"):\n",
    "                return False\n",
    "            for j in range(1, len(i)):\n",
    "                if not i[j].startswith(\"10\"):\n",
    "                    return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
